package 单调栈_上;

import java.util.Arrays;

// 最大矩形
// 给定一个仅包含 0 和 1 、大小为 rows * cols 的二维二进制矩阵
// 找出只包含 1 的最大矩形，并返回其面积
// 测试链接：https://leetcode.cn/problems/maximal-rectangle/

public class Code05_MaximalRectangle {

    public static int MAXN = 201;

    public static int[] heights = new int[MAXN];

    public static int[] stack = new int[MAXN];

    public static int r;

    public int maximalRectangle(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int ans = 0;
        Arrays.fill(heights, 0, m, 0);
        for (int i = 0; i < n; i++) {
            // 来到i行，长方形一定要以i行做底！
            // 加工高度数组(压缩数组)
            for (int j = 0; j < m; j++) {
                // 如果当前行当前列的值是 '0' 那就直接变成0
                // 否则，在上一行的高度上 +1
                heights[j] = grid[i][j] == '0' ? 0 : heights[j] + 1;
            }
            ans = Math.max(largestRectangleArea(m), ans);
        }
        return ans;
    }

    public static int largestRectangleArea(int m) {
        int ans = 0, cur, left;
        r = 0;
        for (int i = 0; i < m; i++) {
            // i -> arr[i]
            while (r > 0 && heights[stack[r - 1]] >= heights[i]) {
                cur = stack[--r];
                left = r == 0 ? -1 : stack[r - 1];
                ans = Math.max(ans, heights[cur] * (i - left - 1));
            }
            stack[r++] = i;
        }
        while (r > 0){
            cur = stack[--r];
            left = r == 0 ? -1 : stack[r - 1];
            ans = Math.max(ans, heights[cur] * (m - left - 1));
        }
        return ans;
    }
}
